package com.cet.algorithm.贪心算法.分发饼干;

import java.util.Arrays;

/**
 * @program: cet-practice
 * @description: 分发饼干
 * @author: 陈恩涛
 * @create: 2023-06-05 21:33
 **/
public class LC455 {

    /**
     * 两个角度；小孩子，饼干
     * 小孩子（胃口越大的孩子最难满足）： 让胃口最大的先去拿最大的饼干
     * 饼干（越小的饼干越难满足小朋友）：把最小的饼干先分给胃口最小的小朋友
     * @param g
     * @param s
     * @return
     */
    public int findContentChildren(int[] g, int[] s) {

        // 小孩子按照胃口进行排序
        Arrays.sort(g);

        // 饼干按照尺寸进行排序
        Arrays.sort(s);

        int gIdx = g.length - 1;

        int sIdx = s.length - 1;

        int result = 0;

        while (gIdx >=0 && sIdx >= 0) {

            // 最大的饼干优先满足胃口最大的孩子
            if (s[sIdx] >= g[gIdx]) {
                sIdx--;
                result++;
            }
            gIdx--;
        }

        return result;
    }

    public static void main(String[] args) {

        LC455 lc455 = new LC455();

        System.out.println(lc455.findContentChildren(new int[]{1, 2}, new int[]{1, 2, 3}));

    }
}
